#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>

using namespace std;

vector<vector<int>> ret;
vector<int> path;
vector<bool> check;

//void dfs(vector<int>& nums)
//{
//    if (path.size() == nums.size())
//    {
//        if (ret.empty())
//        {
//            ret.push_back(path);
//        }
//        else
//        {
//            bool falg = true;
//            for (auto v : ret)
//            {
//                bool change = true;
//                for (int i = 0; i < v.size(); ++i)
//                {
//                    if (path[i] != v[i])
//                    {
//                        change = false;
//                        break;
//                    }
//                }
//                if (change == true)
//                {
//                    falg = false;
//                }
//            }
//            if (falg == true)
//            {
//                ret.push_back(path);
//            }
//        }
//        return;
//    }
//
//    for (int i = 0; i < nums.size(); ++i)
//    {
//        if (check[i] == false)
//        {
//            check[i] = true;
//            path.push_back(nums[i]);
//
//            dfs(nums);
//
//            path.pop_back();
//            check[i] = false;
//        }
//    }
//}
void dfs(vector<int>& nums)
{
    if (path.size() == nums.size())
    {
        ret.push_back(path);
        return;
    }

    for (int i = 0; i < nums.size(); ++i)
    {
        if (check[i] == false && (i == 0 || nums[i] != nums[i - 1] || check[i - 1] == true))
        {
            check[i] = true;
            path.push_back(nums[i]);

            dfs(nums);

            path.pop_back();
            check[i] = false;
        }
    }

}
vector<vector<int>> permuteUnique(vector<int>& nums) {
    check.resize(nums.size(), false);
    sort(nums.begin(), nums.end());
    dfs(nums);

    return ret;
}

int main()
{
    vector<int> nums = { 1 , 1 , 2 };
    permuteUnique(nums);
    
    return 0;
}